//https://leetcode.cn/problems/merge-two-sorted-lists/

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {

    struct ListNode* cur1 = list1, * cur2 = list2;
    struct ListNode* guard = NULL, * tail = NULL;
    guard = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    tail->next = NULL;

    while (cur1 && cur2)
    {
        if (cur1->val < cur2->val)
        {
            tail->next = cur1;
            tail = tail->next;
            cur1 = cur1->next;
        }
        else
        {
            tail->next = cur2;
            tail = tail->next;
            cur2 = cur2->next;
        }
    }

    if (cur1)
    {
        tail->next = cur1;
    }

    if (cur2)
    {
        tail->next = cur2;
    }

    struct ListNode* head = guard->next;
    free(guard);

    return head;

}